package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.TreeSet;

/**
 * @author Fengkai
 * @creat 2023/4/20
 * 考古问题，假设以前的石碑被打碎成了很多块，每块上面都有一个或若干个字符，请你写个程序来把之前石碑上文字可能的组合全部写出来，按升序进行排列。
 * 输入描述:
 * 第一行输入n，n表示石碑碎片的个数。
 * 第二行依次输入石碑碎片上的文字内容s，共有n组。
 * 输出描述:
 * 输出石碑文字的组合(按照升序排列)，行末无多余空格。
 * 示例1   输入输出示例仅供调试，后台判题数据一般不包含示例
 * 输入
 * 3
 * a b c
 * 输出
 * abc
 * acb
 * bac
 * bca
 * cab
 * cba
 */
public class KaoGuWenTi {
    //回溯算法
    public static void main(String[] args) {
        String []inputs = {"a", "b", "a"};
        TreeSet<String> results = kaoGuWenTi(inputs);


    }

    public static TreeSet<String> kaoGuWenTi(String []inputs) {
        TreeSet<String> results = new TreeSet<>();
        boolean dp [] = new boolean[inputs.length];
        dfs(0, dp, results, inputs, new LinkedList<>());
        for (String result : results) {
            System.out.println(result);
        }

        return results;
    }

    private static void dfs(int index, boolean [] dp, TreeSet<String> results, String []inputs, LinkedList<String> cache){
        if (index == inputs.length){
            StringBuilder stringBuilder = new StringBuilder();
            for (String s : cache) {
                stringBuilder.append(s);
            }
            results.add(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < inputs.length; i++) {
            if (dp[i]){
                continue;
            }
            dp[i] = true;
            cache.addLast(inputs[i]);
            dfs(index + 1, dp, results, inputs, cache);
            dp[i] = false;
            cache.removeLast();
        }
    }
}
